#pragma once

#include "stdafx.h"

using namespace std;


/* -------------------------*/
/*           TNode          */
/* -------------------------*/

TNode::TNode()
{
	_parent=_NULL_TNODE;
	_left = _NULL_TNODE;
	_right= _NULL_TNODE;
};

TNode::TNode(int color)
{
	_Color = color;
	_parent=_NULL_TNODE;
	_left = _NULL_TNODE;
	_right= _NULL_TNODE;
	_key="NULL";
	_value="NULL";
};

TNode::~TNode(){;};


TNode* TNode::After()
{
	TNode*node_=this;
	if(node_->_right!=_NULL_TNODE)
	{
		node_=node_->_right;
		while (node_->_left!=_NULL_TNODE){node_=node_->_left;};
		return node_;
	};
	TNode* parent=node_->_parent;
	while (node_==parent->_right){node_=parent;parent=parent->_parent;};
	return parent;
}

TNode* TNode::Before()
{
	TNode*node_=this;
	if (node_->_left!=_NULL_TNODE)
	{
		node_=node_->_left;
		while (node_->_right!=_NULL_TNODE){node_=node_->_right;};
		return node_;
	}
	TNode*parent=node_->_parent;
	while (node_==parent->_left){node_=parent;parent=node_->_parent;};
	return parent;
};


/* Private */
TNode* TNode::_Copy(TNode*parent)
{
	TNode*copy = new TNode();
	copy->_key		=	_key;
	copy->_value	=	_value;
	copy->_Color	=	_Color;
	copy->_parent	=	parent;
	if (_left!=_NULL_TNODE)	{copy->_left=_left->_Copy(copy);};
	if (_right!=_NULL_TNODE){copy->_right=_right->_Copy(copy);};
	return copy;
};

void TNode::_Clear()
{
	_parent=_NULL_TNODE;
	if (_left!=_NULL_TNODE)	{_left->_Clear();}
	if (_right!=_NULL_TNODE){_right->_Clear();};
	delete this;
};













/* -------------------------*/
/*           TMap           */
/* -------------------------*/


TMap::TMap(){_root=_NULL_TNODE;};
TMap::~TMap(){Clear();};

TMap* TMap::Copy()
{
	TMap*copy	=	new TMap();
	copy->_root	=	_root->_Copy(_NULL_TNODE);
	return copy;
};



void TMap::Clear()
{	if (_root=_NULL_TNODE) {return;};
	_root->_Clear();
	_root=_NULL_TNODE;
};

void TMap::Insert (const char* key, const char* value)
{
	TNode*node	=	_root;
	TNode*parent=	_NULL_TNODE;
	int cmp		=	0;
	
	while (node!=_NULL_TNODE)
	{
		parent=node;
		cmp = node->_key.compare(key);
		if (cmp>0)
		{
			node=node->_right;
		}
		else
		{
			if (cmp<0)
			{
				node=node->_left;
			}
			else
			{
				node->_value=value;
				return;
			};
		};
	};
	node			=	new TNode();
	node->_key		=	key;
	node->_value	=	value;
	node->_Color	=	TMap_RED;
	node->_parent	=	parent;
	
	if (parent=_NULL_TNODE)
	{
		_root=node;
		return;
	};
	if (cmp>0)
	{
		parent->_right=node;
	}
	else
	{
		parent->_left=node;
	};
	
	_InsertFixup (node);
};


bool TMap::Contains (const char* key)
{
	TNode*obj=_Find(key);
	return obj!=_NULL_TNODE;
};

const char* TMap::ValueForKey(const char* key)
{
	TNode*node=_Find(key);
	if (node!=_NULL_TNODE) {return node->_value.c_str();};
	return "";
};

bool TMap::Remove(const char* key)
{
	TNode*node=_Find(key);
	if (node==_NULL_TNODE) return false;
	_Remove(node);
	return true;
};

TNode* TMap::First()
{
	TNode*node=_root;
	while (node->_left!=_NULL_TNODE) {node=node->_left;};
	return node;
};

TNode* TMap::Last()
{
	TNode*node=_root;
	while (node->_right!=_NULL_TNODE) {node=node->_right;};
	return node;
};


/* Private */

void TMap::_InsertFixup (TNode*node)
{
	TNode*uncle=_NULL_TNODE;
	while ((node->_parent->_Color==TMap_RED) && (node->_parent->_parent!=_NULL_TNODE))
	{
		if (node->_parent=node->_parent->_parent->_left)
		{
			uncle = node->_parent->_parent->_right;
			if (uncle->_Color==TMap_RED)
			{
				node->_parent->_Color	=	TMap_BLACK;
				uncle->_Color			=	TMap_BLACK;
				uncle->_parent->_Color	=	TMap_RED;
				node					=	uncle->_parent;
			}
			else
			{
				if (node==node->_parent->_right)
				{
					node				=	node->_parent;
					_RotateLeft				(node);
				};
				node->_parent->_Color	=	TMap_BLACK;
				node->_parent->_parent->_Color=TMap_RED;
				_RotateRight				(node->_parent->_parent);
			};
		}
		else
		{
			uncle=node->_parent->_parent->_left;
			if (uncle->_Color==TMap_RED)
			{
				node->_parent->_Color	=	TMap_BLACK;
				uncle->_Color			=	TMap_BLACK;
				uncle->_parent->_Color	=	TMap_RED;
				node					=	uncle->_parent;
			}
			else
			{
				if (node==node->_parent->_left)
				{
					node				=	node->_parent;
					_RotateRight			(node);
				};
				node->_parent->_Color	=	TMap_BLACK;
				node->_parent->_parent->_Color=TMap_RED;
				_RotateLeft					(node->_parent->_parent);
			};
		};
	};

	_root->_Color=TMap_BLACK;
};


void TMap::_RotateLeft(TNode*node)
{
	TNode*child=node->_right;
	node->_right=child->_left;
	if (child->_left!=_NULL_TNODE) child->_left->_parent=node;
	child->_parent=node->_parent;
	if (node->_parent!=_NULL_TNODE)
	{
		if (node==node->_parent->_left)
		{
			node->_parent->_left=child;
		}
		else
		{
			node->_parent->_right=child;
		};
	}
	else
	{
		_root=child;
	};
	child->_left=node;
	node->_parent=child;
}

void TMap::_RotateRight(TNode*node)
{
	TNode*child=node->_left;
	node->_left=child->_right;
	if (child->_right!=_NULL_TNODE) child->_right->_parent=node;
	child->_parent=node->_parent;
	if (node->_parent!=_NULL_TNODE)
	{
		if (node==node->_parent->_right)
		{
			node->_parent->_right=child;
		}
		else
		{
			node->_parent->_left=child;
		};
	}
	else
	{
		_root=child;
	};
	child->_right=node;
	node->_parent=child;
}

TNode* TMap::_Find(const char* key)
{
	TNode*node=_root;
	while (node!=_NULL_TNODE)
	{
		int cmp = node->_key.compare(key);
		if (cmp>0)
		{
			node=node->_right;
		}
		else
		{
			if (cmp<0)
			{
				node=node->_left;
			}
			else
			{
				return node;
			}
		};
	};
	return node;
};


void TMap::_Remove(TNode*node)
{
	TNode*splice;
	TNode*child;
	
	if (node->_left==_NULL_TNODE)
	{
		splice=node;
		child=node->_right;
	}
	else
	{
		if (node->_right==_NULL_TNODE)
		{
			splice=node;
			child=node->_left;
		}
		else
		{
			splice=node->_left;
			while (splice->_right!=_NULL_TNODE)
			{splice=splice->_right;};
			child=splice->_left;
			node->_key=splice->_key;
			node->_value=splice->_value;
		};
	};
	TNode*parent=splice->_parent;
	if (child!=_NULL_TNODE){child->_parent=parent;};
	if (parent==_NULL_TNODE)
	{
		_root=child;
		if (splice!=_NULL_TNODE) delete splice;
		return;
	};
	if (splice==parent->_left)
		{parent->_left=child;}
	else{parent->_right=child;};
	if (splice->_Color==TMap_BLACK) _DeleteFixup(child,parent);
	delete splice;
};

void TMap::_DeleteFixup(TNode*node,TNode*parent)
{
	TNode*sib;
	while ((node!=_root) && (node->_Color==TMap_BLACK))
	{
		if (node==parent->_left)
		{
			sib						=	parent->_right;
			if (sib->_Color==TMap_RED)
			{
				sib->_Color			=	TMap_BLACK;
				parent->_Color		=	TMap_RED;
				_RotateLeft				(parent);
				sib					=	parent->_right;
			};
			if ((sib->_left->_Color==TMap_BLACK) && (sib->_right->_Color==TMap_BLACK))
			{
				sib->_Color			=	TMap_RED;
				node				=	parent;
				parent				=	parent->_parent;
			}
			else
			{
				if (sib->_right->_Color==TMap_BLACK)
				{
					sib->_left->_Color=	TMap_BLACK;
					sib->_Color		=	TMap_RED;
					_RotateRight		(sib);
					sib				=	parent->_right;
				};
				sib->_Color			=	parent->_Color;
				parent->_Color		=	TMap_BLACK;
				sib->_right->_Color	=	TMap_BLACK;
				_RotateLeft				(parent);
				node				=	_root;
			};
		}
		else
		{
			sib						=	parent->_left;
			if (sib->_Color==TMap_RED)
			{
				sib->_Color			=	TMap_BLACK;
				parent->_Color		=	TMap_RED;
				_RotateRight			(parent);
				sib					=	parent->_left;
			}
			if ((sib->_right->_Color=TMap_BLACK)&&(sib->_left->_Color==TMap_BLACK))
			{
				sib->_Color			=	TMap_RED;
				node				=	parent;
				parent				=	parent->_parent;
			}
			else
			{
				if (sib->_left->_Color==TMap_BLACK)
				{
					sib->_right->_Color=TMap_BLACK;
					sib->_Color		=	TMap_RED;
					_RotateLeft			(sib);
					sib				=	parent->_left;
				};
				sib->_Color			=	parent->_Color;
				parent->_Color		=	TMap_BLACK;
				sib->_left->_Color	=	TMap_BLACK;
				_RotateRight			(parent);
				node				=	_root;
			};
		};
	};
	node->_Color	=	TMap_BLACK;
};



/* -------------------------*/
/*         TMap List        */
/* -------------------------*/

TMapIterator::TMapIterator(TMap*map)
{
	_head = map->First();
	_tail = map->Last();
};

TNode* TMapIterator::After(TNode*node)
{
	if (node==_tail) return _NULL_TNODE;
	return node->After();
};
TNode* TMapIterator::Before(TNode*node)
{
	if (node==_head) return _NULL_TNODE;
	return node->Before();
};
